package mo.offer_special;

import java.util.Random;

public class L076 {

    private static final Random RANDOM = new Random();

    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int start = 0, end = nums.length - 1;
        int pivot = getPivot(nums, start, end);
        while (pivot != target) {
            if (pivot > target) {
                end = pivot - 1;
            } else {
                start = pivot + 1;
            }
            pivot = getPivot(nums, start, end);
        }
        return nums[pivot];
    }

    private int getPivot(int[] nums, int start, int end) {
        int random = RANDOM.nextInt(end-start+1) + start;
        swap(nums, random, end);
        int index = start - 1;
        for (int i = start; i < end; i++) {
            if (nums[i] < nums[end]) {
                swap(nums, ++index, i);
            }
        }
        swap(nums, ++index, end);
        return index;
    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

}
